package com.leetcode.offer;

/**
 * @author zfl
 * @Classname SpiralOrder
 * @Description 顺时针打印矩阵
 * @Date 2020/10/19 10:14
 */
public class SpiralOrder {

    /**
     * @param matrix
     * @return
     * 判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 \textit{visited}visited，其中的每个元素表示该位置是否被访问过。
     * 当一个元素被访问时，将visited中的对应位置的元素设为已访问。
     * 时间复杂度O(mn),空间复杂度O(mn)
     */
    public static int[] spiralOrder1(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }

        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int[] order = new int[total];
        int row = 0, column = 0;
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0],nextColumn = column + directions[directionIndex][1];
            if(nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

    /**
     * @param matrix
     * @return
     * 执行用时：1 ms, 在所有 Java 提交中击败了96.71%的用户
     * 内存消耗：39.4 MB, 在所有 Java 提交中击败了99.71%的用户
     */
    public static int[] spiralOrder2(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }

        int left = 0, top = 0, right = matrix[0].length - 1, bottom = matrix.length - 1, k = 0;
        int[] res = new int[(right + 1) * (bottom + 1)];
        while (top <= bottom && left <= right) {
            // 从左至右
            for (int i = left; i <= right; i++) {
                res[k++] = matrix[top][i];
            }
            top++;

            //从上到下
            for (int i = top; i <= bottom; i++) {
                res[k++] = matrix[i][right];
            }
            right--;

            // 从右向左
            for (int i = right; i >= left && top <= bottom; i--) {
                res[k++] = matrix[bottom][i];
            }
            bottom--;

            // 从下往上
            for (int i = bottom; i >= top && left <= right; i--) {
                res[k++] = matrix[i][left];
            }
            left++;
        }
        return res;
    }
}
